/**
 * 
 */
package Phase2;

import java.io.FileOutputStream;
import java.io.ObjectStreamException;
import java.io.Serializable;
import java.util.Iterator;
import Phase1.GlobalID;

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.concurrent.Semaphore;

import org.junit.Assert;

import plugin.Visitor;

/**
 * 
 * A member of a HyPeerWeb with a binary identifier
 * 
 * @author rpadilla
 *
 */

public class Node implements NodeOrRange, Comparable<Node>, Serializable
{
	private static final long serialVersionUID = 1L;
	protected GlobalID globalID;
	protected int id;
	private volatile Semaphore access;
	private volatile Semaphore modifyingCommands;
	private Node fold;
	private Node oldFold;	
	private NodeList up;
	private NodeList down;
	private NodeList neighbours;
	private NodeState state;
	private Map<String, Object> payload;
	private boolean beingModified;
	private volatile int accessingData;
	
	
	/**
	 * default constructor
	 * @pre None
	 * @post all lists are instantiated and folds are assigned to null
	 */
	public Node()
	{
		this.init();
	}
	
	public Node(int port)
	{
		this.init(port);
	}

	private void init(int port)
	{
		this.globalID = new GlobalID(port);
		this.init();
	}
	
	private void init()
	{
		this.access = new Semaphore(0, true);
		this.modifyingCommands = new Semaphore(0, true);
		if (this.globalID == null)
		{
			this.globalID = new GlobalID();
		}
		
		this.up = new NodeList();
		this.down = new NodeList();
		this.neighbours = new NodeList();
		this.fold = this;
		this.oldFold = null;
		
		this.state = EmptyState.getState();
		
		this.payload = new HashMap<String, Object>();
		this.access = new Semaphore(0, true);
		this.beingModified = false;
		this.accessingData = 0;
		
/*		ObjectDB dataBase = ObjectDB.getDatabase();
		dataBase.put(globalID, this);*/
	}
	
	/**
	 * compares one Node to another
	 * @param other - Node to compare to
	 * @pre other != null
	 * @post return -1 if this < other | 0 if this == other | or 1 if this > other	 * 
	 *
	 */
	public int compareTo(Node other)
	{
		assert other != null;
		
		boolean rootAccess = true;
		
		int result = 0;
		try
		{
			if (this.getId(true) < other.getId(rootAccess))
			{
				result = -1;
			}
			else if (this.getId(true) > other.getId(rootAccess))
			{
				result = 1;
			}
		}
		//This exception should never be thrown with the parameter set to true
		catch (InterruptedException e)
		{
			;
		}
		
		return result;
	}
	
	/**
	 * Gets the GlobalID
	 * @return returns the GlobalID associated with this node
	 * @pre none
	 * @post return the GlobalID
	 */
	public GlobalID getGlobalID()
	{
		return this.globalID;
	}
	
	/**
	 * Returns the current NodeState that the node is in
	 * @return The current state that the node is in
	 * @pre None
	 * @post return current state
	 */
	public NodeState getState(boolean rootAccess) throws InterruptedException
	{
		while (!rootAccess && beingModified)
		{
			access.acquire();
		}
		return this.state;
	}
	
	/**
	 * Sets the Node state as the parameter state
	 * @param state New State the Node will be set to
	 * @pre None
	 * @post this.state = state
	 */
	public void setState(NodeState state) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
		this.state = state;
	}
	
	/**
	 * Returns a NodeList of this node's upPointers
	 * @return NodeList of upPointers
	 * @throws InterruptedException 
	 * @pre None
	 * @post return the list of up pointers
	 */
	public NodeList getUpPointers(boolean rootAccess) throws InterruptedException 
	{
		while (!rootAccess && beingModified)
		{
			access.acquire();
		}
		return this.up;
		
	}

	/**
	 * adds all the up pointers to the NodeList that is passed in
	 * @param up - The NodeList of pointers that will be assigned
	 * @pre None
	 * @post this.up = up
	 */
	public void addUpPointers(NodeList up) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
		this.up.addAll(up);
	}
	
	/**
	 * Sets all the up pointers to the NodeList that is passed in
	 * @param up - The NodeList of pointers that will be assigned
	 * @pre None
	 * @post this.up = up
	 */
	public void setUpPointers(NodeList up) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
		this.up = new NodeList();
		this.up.addAll(up);
	}
	
	/**
	 * Adds an up pointer to the list
	 * @param node
	 * @pre node != null
	 * @post node is added to the list of up pointers
	 */
	public void setUpPointer(Node node) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		assert node != null;
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
		
		this.up.add(node);
	}
	
	/**
	 * returns the list of down pointers
	 * @return return NodeList of down pointers
	 * @pre none
	 * @post return list of down pointers
	 */
	public NodeList getDownPointers(boolean rootAccess) throws InterruptedException
	{
		while (!rootAccess && beingModified)
		{
			access.acquire();
		}
		return down;
	}	
	
	/**
	 * adds the param down to the list of down pointers
	 * @param down - list of nodes to set as down pointer list
	 * @pre none
	 * @post this.down = down	 * 
	 */
	public void addDownPointers(NodeList down) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
		this.down.addAll(down);
	}
	
	/**
	 * sets the list of down pointers
	 * @param down - list of nodes to set as down pointer list
	 * @pre none
	 * @post this.down = down	 * 
	 */
	public void setDownPointers(NodeList down) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
		this.down = new NodeList();
		this.down.addAll(down);
	}	
	/**
	 * adds a node to the down pointers
	 * @param down - node to add to list of down pointers
	 * @pre down != null
	 * @post down is added to the list of down pointers
	 */
	public void setDownPointer(Node down) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		assert down != null;
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
		
		this.down.add(down);
	}
	/**
	 * gets the list of neighbours
	 * @return list of neighbours
	 * @pre none
	 * @post returns list of neighbours
	 */
	public NodeList getNeighbours(boolean rootAccess) throws InterruptedException
	{
		while (!rootAccess && beingModified)
		{
			access.acquire();
		}
		return neighbours;
	}
	
	/**
	 * @param id - id of neighbour to get
	 * @return node with specified id
	 * @pre none
	 * @post return node with specified id,
	 * otherwise if not found return null
	 */
	public Node getNeighbour(int id, boolean rootAccess) throws InterruptedException
	{

		while (!this.acquireAccessPriviledge(rootAccess))
		{
			access.acquire();
		}
		Node result = null;
		NodeList neighbour = this.getNeighbours(rootAccess);
		for(Node node : neighbour)
		{
			if(node.getId(rootAccess) == id)
			{
				result = node;
				break;
			}
		}
		this.releaseAccessPriviledge();
		return result;
	}
	
	/**
	 * adds the parameter neighbours to this node's neighbours
	 * @param neighbours
	 * @pre none
	 * @post this.neighbours = neighbours
	 */
	
	public void addNeighbours(NodeList neighbours) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
		this.neighbours.addAll(neighbours);
	}
	
	/**
	 * sets the neighbours for this node
	 * @param neighbours
	 * @pre none
	 * @post this.neighbours = neighbours
	 */
	public void setNeighbours(NodeList neighbours) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
		this.neighbours = new NodeList();
		this.neighbours.addAll(neighbours);
	}
	
	/**
	 * adds a neighbour
	 * @param neighbour - neighbour to be added
	 * @pre neighbour != null
	 * @post neighbour added to list of neighbours
	 */
	public void addNeighbour(Node neighbour) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
		assert neighbour != null;
		
		this.neighbours.add(neighbour);
	}
	
	/**
	 * gets the current fold
	 * @return the current fold
	 * @pre none
	 * @post returns the current fold
	 */
	public Node getFold(boolean rootAccess) throws InterruptedException
	{
		while (!rootAccess && beingModified)
		{
			access.acquire();
		}
		return fold;
	}
	
	/**
	 * sets the fold
	 * @param fold - fold to be set
	 * @pre fold != null
	 * @post this.fold = fold
	 */
	public void setFold(Node fold) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		assert fold != null;
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
		
		this.fold = fold;
	}
	
	/**
	 * gets the old fold
	 * @return the old fold
	 * @pre none
	 * @post returns the old fold
	 */
	public Node getOldFold() 
	{
		return oldFold;
	}
	/**
	 * sets the old fold
	 * @param oldFold - fold to be set
	 * @pre fold != null
	 * @post this.oldFold = oldFold
	 */	
	public void setOldFold(Node oldFold) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		assert fold != null;
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
		
		this.oldFold = oldFold;
	}
	
	/**
	 * returns the id of the node
	 * @return the id of the node
	 * @pre None
	 * @post return id of node
	 */
	public int getId(boolean rootAccess) throws InterruptedException 
	{
		/*while(!rootAccess && beingModified)
		{
			access.acquire();
		}*/
		return id;
	}
	
	/**
	 * sets the id of the node
	 * @param id - id to be set
	 * @pre 0 <= id < 2^(height + 1) if in Empty State or Last State or 0 <= id < 2^height otherwise. (id is then valid)
	 * @post this.id = id
	 */
	public void setId(int id) throws InterruptedException
	{
		Assert.assertTrue(beingModified);
		while (this.accessingData > 0)
		{
			modifyingCommands.acquire();
		}
/*		if(this.getState() instanceof EmptyState || this.getState() instanceof LastState)
		{
			assert id < Math.pow(2, this.getHeight() + 1) && id >= 0;

		}
		else
		{
			assert id < Math.pow(2, this.getHeight()) && id >= 0;
		}*/
		this.id = id;
	}
	
	/**
	 * return the height of the node
	 * @return the height of the node
	 * @pre None
	 * @post returns the height of the node
	 */
	public int getHeight(boolean rootAccess) throws InterruptedException
	{
		while (!this.acquireAccessPriviledge(rootAccess))
		{
			access.acquire();
		}
		int result;
		if(this.down.size() > 0)
		{
			result = this.down.size() + this.neighbours.size();
		}
		else
		{
			result = this.neighbours.size();
		}
		this.releaseAccessPriviledge();
		
		return result;
		
	}
	
	/**
	 * returns the parent of the node
	 * @return parent of the node
	 * @pre This Node has a parent
	 * @post return node with id half of this node(always rounding down)
	 */
	public Node getParent(boolean rootAccess) throws InterruptedException
	{
		//assert this.getState(rootAccess).toString().compareTo("EmptyState") != 0;
		
		if(!this.acquireAccessPriviledge(rootAccess))
		{
			access.acquire();
		}
		
		int possibleParent = this.getId(rootAccess) ^ (int) (Math.pow(2, getHeight(rootAccess) - 1));
		if(possibleParent < this.id)
		{
			Node neighbour = this.getNeighbour(possibleParent, rootAccess);
			this.releaseAccessPriviledge();
			return neighbour;
		}
		else
		{
			this.releaseAccessPriviledge();
			return null;
		}		
	}
	

	/**
	 * Gets the child of the node
	 * @return child of node
	 * @pre none
	 * @post return the child node or null if there is no child
	 */
	public Node getChild(boolean rootAccess) throws InterruptedException
	{
		boolean allSatisfied = false;
		Node child = null;
		while (!allSatisfied)
		{
			boolean[] satisfied = new boolean[2];
			satisfied[0] = this.acquireAccessPriviledge(rootAccess);
			allSatisfied = satisfied[0];
			if(allSatisfied)
			{
				child = neighbours.getMax();
				satisfied[1] = child.acquireAccessPriviledge(rootAccess);
				allSatisfied = satisfied[1];
			}
			if(!allSatisfied)
			{
				if(satisfied[0])
				{
					this.releaseAccessPriviledge();
				}
				if(satisfied[1])
				{
					child.releaseAccessPriviledge();
				}
				access.acquire();
			}
		}
		if(neighbours.getMax() != null
				&& child.getId(rootAccess) == (this.getId(rootAccess) + (int) (Math.pow(2, this.getHeight(rootAccess) - 1)))
				&& child.getState(rootAccess) instanceof DownState)
		{
			this.releaseAccessPriviledge();
			child.releaseAccessPriviledge();
			return child;
		}
		else
		{
			this.releaseAccessPriviledge();
			child.releaseAccessPriviledge();
			return null;
		}
	}
	/**
	 * Returns the Node that logically would be the child without checking the Node state to see if it actually is a Child
	 * @return The Node whose Id would be child or null if that Node does not exist
	 * @pre none
	 * @post Return the Node whose Id == the id of the theoretical child or null if that Node does not exist
	 */
	public Node giveMeChild(boolean rootAccess) throws InterruptedException
	{
		if(!this.acquireAccessPriviledge(rootAccess))
		{
			access.acquire();
		}
		Node child = this.getNeighbours(rootAccess).getMax();
		if(child != null && child.getId(rootAccess) == (this.getId(rootAccess) + (int) (Math.pow(2, this.getHeight(rootAccess) - 1)))
		)
		{
			this.releaseAccessPriviledge();
			return child;
		}
		else
		{
			this.releaseAccessPriviledge();
			return null;
		}
	}
	
	public Object getPayload(String id)
	{
		return this.payload.get(id);
	}
	
	public Object setPayload(String id, Object obj)
	{
		return this.payload.put(id, obj);
	}
	
	public Map<String, Object> getWholePayload()
	{
		return this.payload;
	}
	
	public void setWholePayload(Map<String, Object> payload)
	{
		this.payload = payload;
	}
	
	public void accept(Visitor v, Object i) throws InterruptedException
	{
		v.visit(this, i);
	}
	
	public Object acceptWithResponse(Visitor v, Object i) throws InterruptedException
	{
		return v.visit(this, i);
	}

	/**
	 * returns the range or node to "right" of node
	 * @param callingNode - node to find it's "right" neighbour
	 * @return the range or node to "right" of node
	 * @pre callingNode != null
	 * @post return the range or node to "right" of node
	 */
	public NodeOrRange goRight(Node callingNode, boolean rootAccess) throws InterruptedException
	{
		assert callingNode != null;
		
		while (!state.lockState(callingNode, rootAccess))
		{
			access.acquire();
		}
		NodeOrRange result = state.goRight(callingNode, rootAccess);
		//this.releaseAccessPriviledge();
		return result;
	}
	
	/**
	 * Returns the Node where the insertion Node should be inserted
	 * @return the insertion point in the hypeer web
	 * @pre none
	 * @post returns Node that is the insertion point for a new Node
	 */
	
	public Node getInsertionPoint() throws InterruptedException
	{
		boolean rootAccess = false;
		try
		{
			NodeOrRange node;
			node = goRight(this, rootAccess);
			if(node == null && this.id == 0)
			{
				this.setPayload("busy", new Semaphore(0, true));
				
				return this;
			}
			while (node instanceof Node)
			{
				node = ((Node) node).goRight((Node) node, rootAccess);
			}
			//System.out.println("Range now found.");
			InsertionRange range = (InsertionRange) node;
			Node midrange;
			//all return values to goRight(..) will now be a Range
			while (range.getLowerBound() != range.getUpperBound().getId(rootAccess))
			{
				int mid = Math.round((range.getLowerBound() + range.getUpperBound().getId(rootAccess)) / 2);
				midrange = find(mid, range.getUpperBound(), rootAccess);
				if(midrange.getChild(rootAccess) != null)
				{
					range.setLowerBound(midrange.getId(rootAccess) + 1);				
				}
				else
				{
					range.setUpperBound(midrange);
				}
			}
			Node insertionPoint = range.getUpperBound();
			
			if(insertionPoint.getInsertionLock())
			{
				return insertionPoint;
			}
			else
			{
				return null;
			}
		}
		catch (IllegalStateException e)
		{
			throw new NullPointerException("Error finding Insertion Point.");
		}
	}
	
	/**
	 * Traverses the HypeerWeb starting at nextNode until it finds a node whose getId() == id
	 * @param id An integer representing the Node ID that is being searched for
	 * @param nextNode The Node in the Hypeer Web where the search for the parameter id starts
	 * @return the Node in the Hypeer Web whose getId() == id
	 * @pre nextNode != null && id >= 0
	 * @post return Node whose getId() == id if such a node exists in the hypeer web
	 */
	
	public static Node find(int id, Node nextNode, boolean rootAccess) throws InterruptedException
	{
		assert nextNode != null && id >= 0;
		
		Node answer = nextNode;
		Iterator<Node> iter = nextNode.getNeighbours(rootAccess).iterator();
		for(; iter.hasNext() && answer.getId(rootAccess) != id;)
		{
			//Node height and number of neighbors are the same so no indexing problems here
			Node neighbour = iter.next();
			int targetBit = neighbour.getId(rootAccess) ^ nextNode.getId(rootAccess);
			if(neighbour.getId(rootAccess) == id)
			{
				return neighbour;
			}
			//Checks to see if this neighbour is one closer to the target id
			else if(neighbour.getId(rootAccess) != id && ((neighbour.getId(rootAccess) & targetBit) == (id & targetBit)))
			{
				answer = find(id, neighbour, rootAccess);
			}
		}
		if(answer.getId(rootAccess) == id)
		{
			return answer;
		}
		else
		{
			//should never be reached unless find is call external to the Node Class
			return null;
		}
	}
	
	/**
	 * inserts the node into the HyPeerWeb
	 * @param insertNode - node to be inserted
	 * @pre insertNode != null
	 * @post insertNode is now the last node in the HyPeerWeb and satisfies the UML diagram
	 */
	public void insert(Node insertNode) throws InterruptedException
	{
		assert insertNode != null;
		
		Node insertionPoint = null;
		while (insertionPoint == null)
		{
			try
			{
				insertionPoint = this.getInsertionPoint();
			}
			catch (NullPointerException e)
			{
				System.out.println("Error trying to find Insertion Point. Trying again.");
			}
		}
		insertionPoint.performInsert(insertNode);
	}
	
	public void performInsert(Node insertNode) throws InterruptedException
	{
		try
		{
			FileOutputStream fos = new FileOutputStream("log.txt", true);
			java.io.PrintStream oos = new java.io.PrintStream(fos);
			oos.print("Starting insert at insertion point " + this.id + "\n");
		}
		catch (java.io.IOException e)
		{
			System.out.println("Error writing removal string to file.");
		}
		
		boolean rootAccess = true;
		insertNode.beingModified(true);
		this.beingModified(true);
		this.fold.beingModified(true);
		if(this.oldFold != null)
		{
			this.oldFold.beingModified(true);
		}
		NodeList insertionUpPointers = this.getUpPointers(rootAccess);
		NodeList insertionNeighbours = this.getNeighbours(rootAccess);
		for(Node neighbour : insertionNeighbours)
		{
			neighbour.beingModified(true);
		}
		for(Node upPointer : insertionUpPointers)
		{
			upPointer.beingModified(true);
		}
		
		insertNode.setId(this.getId(rootAccess) + (int) Math.pow(2, this.getHeight(rootAccess)));
		
		this.insertionFoldSetup(this, insertNode);

		if(insertNode.getFold(rootAccess).getId(rootAccess) != 0)
		{
			for(Node node : this.getNeighbours(rootAccess))
			{
				if(node.getChild(rootAccess) == null)
				{
					insertNode.setDownPointer(node);
					node.setUpPointer(insertNode);
					node.setState(UpState.getState());
				}
			}
		}
		
		if(insertionUpPointers.size() > 0)
		{
			insertNode.addNeighbours(insertionUpPointers);
			for(Node node : insertionUpPointers)
			{
				NodeList downPointers = node.getDownPointers(rootAccess);
				downPointers.remove(this);
				node.setDownPointers(downPointers);
				node.addNeighbour(insertNode);
				if(node.getDownPointers(rootAccess).size() == 0)
				{
					node.setState(EmptyState.getState());
				}
				node.beingModified(false);
			}
			insertionUpPointers.clear();
			this.setUpPointers(insertionUpPointers);
			this.setState(EmptyState.getState());
		}
		
		//sets this node as added Node's parent
		insertNode.addNeighbour(this);
		//set insertNode as child
		this.addNeighbour(insertNode);

		insertNode.renewState();
		
		for(Node neighbour : insertionNeighbours)
		{
			neighbour.beingModified(false);
		}
		this.beingModified(false);
		insertNode.beingModified(false);
		this.fold.beingModified(false);
		insertNode.getFold(rootAccess).beingModified(false);
		if(this.oldFold != null)
		{
			this.oldFold.beingModified(false);
		}
		
		try
		{
			FileOutputStream fos = new FileOutputStream("log.txt", true);
			java.io.PrintStream oos = new java.io.PrintStream(fos);
			oos.print("Ending insert at insertion point " + this.id + "\n");
		}
		catch (java.io.IOException e)
		{
			System.out.println("Error writing removal string to file.");
		}
		
		synchronized (this)
		{
			Semaphore lock = (Semaphore) this.getPayload("busy");
			lock.release();
			
			//sets payload in the next Insertion Point
			Node nextInsertion = new Node();
			if(this.id == (int) Math.pow(2, neighbours.size() - 1) - 1)
			{
				if(this.id != 0)
				{
					nextInsertion = find(0, this, rootAccess);
					nextInsertion.setPayload("busy", lock);
					this.setPayload("busy", null);
				}
				else
				{
					this.setPayload("busy", lock);
				}
			}
			else
			{
				nextInsertion = find(this.id + 1, this, rootAccess);
				nextInsertion.setPayload("busy", lock);
				this.setPayload("busy", null);
			}
		}
	}
	
	/**
	 * Sets the fold and old fold of the insertion point Node and the node that is to be inserted
	 * appropriately
	 * @param insertionPoint the Node where a new Node will be inserted
	 * @param insertNode The new Node that is being inserted into the Hypeer Web
	 * @pre insertionPoint is the insertion Point in the Hypeer Web this Node is connected to.
	 * insertNode is a new Node that is being inserted into the current Hypeer Web.
	 * @post The fold and old fold are set correctly in insertionPoint and insertNode
	 */
	public void insertionFoldSetup(Node insertionPoint, Node insertNode)throws InterruptedException
	{
		boolean rootAccess = true;
		
		Assert.assertTrue(insertNode.getDownPointers(rootAccess).size() == 0 
				&& insertNode.getUpPointers(rootAccess).size() == 0 
				&& insertNode.getNeighbours(rootAccess).size() == 0);
		//assert this.getInsertionPoint() == insertionPoint;
		
		//set folds
		// first case is for the first insert in a size one HyPeerWeb
		if(insertionPoint.getFold(rootAccess).getId(rootAccess) == insertionPoint.getId(rootAccess))
		{
			insertNode.setFold(insertionPoint);
			insertionPoint.setFold(insertNode);
		}
		else
		{
			if(insertionPoint.getOldFold() == null)
			{
				insertNode.setFold(insertionPoint.getFold(rootAccess));
				insertionPoint.getFold(rootAccess).setFold(insertNode);
				insertionPoint.getFold(rootAccess).setOldFold(insertionPoint);
			}
			else
			{
				insertNode.setFold(insertionPoint.getOldFold());
				insertNode.getFold(rootAccess).setFold(insertNode);
				insertionPoint.setOldFold(null);
			}
		}
	}	
	
	/**
	 * returns string representation of this node
	 * @return string representation of this node
	 * @pre None
	 * @post return string representation of this node 
	 */
	public String toString()
	{
		String result;
		boolean rootAccess = false;
		try
		{
			result = "[Node: " + this.getId(rootAccess) + "]";
		 
			result += String.format("%-25s", " Neighbours: " 
					+ (getNeighbours(rootAccess) == null ? "" : getNeighbours(rootAccess).toString()));  
			result += String.format("%-21s",  " Up: " 
					+ (this.getUpPointers(rootAccess) == null ? "" : this.getUpPointers(rootAccess).toString())); 
			result += String.format("%-25s", " Down: " 
					+ (this.getDownPointers(rootAccess) == null ? "" : this.getDownPointers(rootAccess).toString())); 
			result += String.format("%-10s", "	Fold: " 
					+ (this.getFold(rootAccess) == null ? "<>" : this.getFold(rootAccess).getId(rootAccess))); 
			result += String.format("%-20s", " OldFold: " 
					+ (this.getOldFold() == null ? "<>" : this.getOldFold().getId(rootAccess))); 
			result += String.format("%-20s", " State: <" + this.getState(rootAccess) + ">");
		}
		catch (InterruptedException e)
		{
			result = "Node was in an invalid state and this thread terminated before a valid state was reached.";
		}
		return result;
		//return "Node: " + id;
		
	}
	/**
	 * Prints all nodes in a Hypeer Web connected to this node
	 * @return string representation of the HyPeerWeb
	 * @pre None
	 * @post return string representation of all nodes connected to this node
	 */
	@SuppressWarnings("unchecked")
	public String printAllNode() throws InterruptedException
	{
		boolean rootAccess = false;
		
		ArrayList<Node> recipients = new ArrayList<Node>();
		plugin.BroadcastAlgorithm broadcast = new plugin.BroadcastAlgorithm();
		recipients = (ArrayList<Node>) this.acceptWithResponse(broadcast, this.getId(rootAccess));
		
		NodeList allNodes = new NodeList();
		allNodes.addAll(this.allNodes(recipients, this.getId(rootAccess)));
		
		String result = "";
		for(Node node : allNodes)
		{
			result += node.toString() + "\n";
		}
		
		return result;
	}

	/**
	 * Returns list of all nodes connected to this one
	 * @return all nodes connected to this one
	 * @pre current node/up/down/neighbor not null
	 * @post return list of nodes connected to this one
	 */
	@SuppressWarnings("unchecked")
	private NodeList allNodes(ArrayList<Node> recipients, int startNodeID) throws InterruptedException
	{
		//assert this.getUpPointers() != null && this.getDownPointers() != null && this.getNeighbours() != null; 
		
		plugin.BroadcastAlgorithm broadcast = new plugin.BroadcastAlgorithm();
		NodeList result = new NodeList();
		ArrayList<Node> nextRecipients = new ArrayList<Node>();
		
		result.add(this);
		for(Node node : recipients)
		{
			nextRecipients = (ArrayList<Node>) node.acceptWithResponse(broadcast, startNodeID);
			result.addAll(node.allNodes(nextRecipients, startNodeID));
		}
		
		return result;
	}
	
	/**
	 * This method removes the node from the HyPeerWeb 
	 * and replaces it with the last node from the HyPeerWeb
	 * @return the node that replaced the removed Node
	 * @pre this node is part of a HyPeerWeb and this node's height is 
	 * greater than 0
	 * @post return the Node that was removed from HyPeerWeb
	 */
	public Node remove() throws InterruptedException
	{
		boolean rootAccess = true;
		assert this.getHeight(rootAccess) > 0;
		
		Node insertionPoint = null;
		while (insertionPoint == null)
		{
			try
			{
				insertionPoint = this.getInsertionPoint();
			}
			catch (NullPointerException e)
			{
				System.out.println("Error finding Insertion Point. Trying again.");
			}
			
		}

		try
		{
			FileOutputStream fos = new FileOutputStream("log.txt", true);
			java.io.PrintStream oos = new java.io.PrintStream(fos);
			oos.print("Starting removal of " + this.id + "\n");
		}
		catch (java.io.IOException e)
		{
			System.out.println("Error writing removal string to file.");
		}
		//set All Nodes to be changed to the invalid State
		NodeList modified = new NodeList();
		this.beingModified(true);
		modified.add(this);
		for(Node node : this.neighbours)
		{
			node.beingModified(true);
			modified.add(node);
		}
		for(Node node : this.up)
		{
			node.beingModified(true);
			modified.add(node);
		}
		for(Node node : this.down)
		{
			node.beingModified(true);
			modified.add(node);
		}
		this.fold.beingModified(true);
		modified.add(this.fold);
		if(this.oldFold != null)
		{
			this.oldFold.beingModified(true);
			modified.add(this.oldFold);
		}
				
		Node lastNode = insertionPoint.getLastNode();
		//get previous insertion point
		Node prevInsertionPoint = lastNode.getParent(rootAccess);
		if(prevInsertionPoint == this)
		{
			prevInsertionPoint = lastNode;
		}
		lastNode.beingModified(true);
		modified.add(lastNode);
		prevInsertionPoint.beingModified(true);
		modified.add(prevInsertionPoint);
		modified.addAll(lastNode.getNeighbours(rootAccess));
		modified.addAll(lastNode.getDownPointers(rootAccess));
		modified.add(lastNode.getFold(rootAccess));
		lastNode.removeLastNode();
		//System.out.println("After removing last node: \n" + this.printAllNode());
		
		Node returnNode = lastNode.equals(this) ? this : lastNode.replaceNode(this);
		
		synchronized (this)
		{
			//unlock insertion Point and set in the new Insertion Point
			Semaphore lock = (Semaphore) insertionPoint.getPayload("busy");
			lock.release();
			prevInsertionPoint.setPayload("busy", lock);
			insertionPoint.setPayload("busy", null);
		}
		
		try
		{
			FileOutputStream fos = new FileOutputStream("log.txt", true);
			java.io.PrintStream oos = new java.io.PrintStream(fos);
			oos.print("Ending removal of " + this.id + "\n");
		}
		catch (java.io.IOException e)
		{
			System.out.println("Error writing removal string to file.");
		}
		
		for(Node node : modified)
		{
			node.beingModified(false);
		}
		
		return returnNode;
	}
	
	public Object writeReplace() throws ObjectStreamException
	{
		NodeProxy p = new NodeProxy(this.globalID, this.id);
		return p;
	}
	
	public NodeProxy getProxy()
	{
		return new NodeProxy(this.globalID, this.id);
	}
	
	/**
	 * Returns the last Node in the Hypeer Web
	 * @return Node object that is the Last Node in the Hypeer Web the current Node is connected to.
	 * @pre The Node that calls this function is the Insertion Point
	 * @post Last Node in the HypeerWeb this Node is connected to is returned.
	 */
	public Node getLastNode() throws InterruptedException
	{
		boolean rootAccess = true;
		if(this.getId(rootAccess) == 0 && this.getNeighbours(rootAccess).size() == 0)
		{
			return this;
		}
		else if(this.getId(rootAccess) == 0)
		{
			return this.getFold(rootAccess);
		}
		else
		{
			Node tmp = find(this.getId(rootAccess) - 1, this, rootAccess);
			return tmp.getChild(rootAccess);
		}
		
	}
	/**
	 * Removes the current Node from the Hypeer Web by removing all it's pointers to other Nodes.
	 * @return The Node just removed from it's position in the Hypeer Web
	 * @pre the calling Node is the Node with the highest ID in the hypeer web
	 * @post 
	 */
	public Node removeLastNode() throws InterruptedException
	{
		boolean rootAccess = true;
		
		for(Node neighbour : this.neighbours)
		{
			neighbour.beingModified(true);
		}
		for(Node downPointer : this.down)
		{
			downPointer.beingModified(true);
		}
		this.fold.beingModified(true);
		
		//this will change to emptystate
		//System.out.println("--" +  getId());
		this.setState(EmptyState.getState());
		//neighbors remove this and point to my surgate
		Iterator<Node> it = this.getNeighbours(rootAccess).iterator();
		while (it.hasNext())
		{
			Node temp = it.next();
			temp.removeNeighbor(this);
			
		}
		
		//if no neighbor, then the down nodes will change to downstate.
		//down pointers should remove their pointer to lastNode
		it = this.getDownPointers(rootAccess).iterator();
		while (it.hasNext())
		{
			Node temp = it.next();
			temp.removeUp(this);
		}
		//last node has no up pointers, right?
		
		if(this.getFold(rootAccess) != null)
		{
			this.getFold(rootAccess).removeFold(this);
		}
		//fold.fold = fold.oldfold
		//fold.oldfold= null
		
		return this;
	}
	
	/**
	 * 
	 * @param node The node that is being removing 
	 */
	public void removeNeighbor(Node node) throws InterruptedException
	{	 
		boolean rootAccess = true;
		
		if(this.equals(node.getParent(rootAccess)))
		{ 	
			NodeList nei = node.getNeighbours(rootAccess);
		 	this.getUpPointers(rootAccess).addAll(nei);
		 	this.getUpPointers(rootAccess).remove(this);
		 	this.setState(UpState.getState());
		}
		else
		{
			this.getDownPointers(rootAccess).add(node.getParent(rootAccess));
			this.setState(DownState.getState());
	
		}
		
		this.getNeighbours(rootAccess).remove(node);
		
		
		renewState();
		
	}
	/**
	 * Removes an Up Pointers from the current Node to the parameter, node
	 * @param node
	 * @pre node != null
	 * @post current Node no longer has an Up Pointer to node && state of current Node is updated correctly
	 */
	public void removeUp(Node node) throws InterruptedException
	{  
		assert node != null;
		boolean rootAccess = true;
		
		this.getUpPointers(rootAccess).remove(node);
		
		if(this.getUpPointers(rootAccess).size() == 0)
		{
			this.setState(DownState.getState());
		}
		renewState();
	}
	/**
	 * remove the fold into it previous step
	 * @param node
	 * 
	 */
	public void removeFold(Node node) throws InterruptedException
	{ 
		//System.out.println("f"+id +" " + fold + "|" + oldFold+"child"+giveMeChild());
		boolean rootAccess = true;
		if(this.giveMeChild(rootAccess) != null)
		{
			//System.out.println("giveMeChild() != null");
			this.setFold(node.getParent(rootAccess));
			this.setOldFold(null);
			this.getFold(rootAccess).setOldFold(this);
			Node child = this.giveMeChild(rootAccess);
			 
			this.getFold(rootAccess).setFold(child);
		} 
		else
		{
			this.setFold(node.getParent(rootAccess));
			this.setOldFold(null);
			this.getFold(rootAccess).setOldFold(null);
		}
		//System.out.println(this.getId() + "'s Fold updated to: " + fold.getId());
		renewState();
	}
	/**
	 * 
	 * Determine the current state and reassign it 
	 * @pre none
	 * @post state of the current node is assigned correctly
	 */
	public void renewState() throws InterruptedException
	{
		boolean rootAccess = true;
		if(this.getUpPointers(rootAccess).size() == 0 && this.getDownPointers(rootAccess).size() == 0)
		{
			this.setState(EmptyState.getState());
			if (this.getNeighbours(rootAccess).size() > 0 
					&& this.getId(rootAccess) > this.getNeighbours(rootAccess).getMax().getId(rootAccess))
			{
				this.setState(LastState.getState());
			}
			
		} 
		else if(this.getUpPointers(rootAccess).size() > 0)
		{
			this.setState(UpState.getState());
		}
		else if(this.getDownPointers(rootAccess).size() > 0)
		{
			this.setState(DownState.getState());
		}
		else
		{
			this.setState(EmptyState.getState());
		}
	}
	
	/**
	 * Replaces the passed in Node with itself
	 * @param other the Node to replace
	 * @return this Node
	 * @pre other != null;
	 * @post All pointers in the Node, other, are transfered to the current Node
	 */
	public Node replaceNode(Node other) throws InterruptedException
	{
		assert other != null;
		
		boolean rootAccess = true;
		this.id = other.getId(rootAccess);		
		this.state = other.getState(rootAccess);
		
		this.neighbours.clear();
		this.neighbours.addAll(other.getNeighbours(rootAccess));
		
		this.up.clear();
		this.up.addAll(other.getUpPointers(rootAccess));
		
		this.down.clear();
		this.down.addAll(other.getDownPointers(rootAccess));
		
		this.fold = other.getFold(rootAccess);
		this.oldFold = other.getOldFold();
		
		this.payload.clear();
		this.payload.putAll(other.getWholePayload());
		
		// update neighbour pointers
		for (Node neighbour : this.neighbours)
		{
			NodeList neighbourNodeList = neighbour.getNeighbours(rootAccess);
			neighbourNodeList.replace(other, this);
			neighbour.setNeighbours(neighbourNodeList);
		}
		// update down pointers to this node
		for (Node upPointer : this.up)
		{
			NodeList upPointerNodeList = upPointer.getDownPointers(rootAccess);
			upPointerNodeList.replace(other, this);
			upPointer.setDownPointers(upPointerNodeList);
		}
		// update up pointers to this node
		for (Node downPointer : this.down)
		{
			NodeList downPointerNodeList = downPointer.getUpPointers(rootAccess);
			downPointerNodeList.replace(other, this);
			downPointer.setUpPointers(downPointerNodeList);
		}
		
		// updates folds, takes care of case where this 
		// might be the fold's oldFold
		if (this.fold.getFold(rootAccess).compareTo(other) == 0)
		{
			this.fold.getFold(rootAccess).setFold(this);
			this.fold.setFold(this);
		}
		else if (this.fold.getOldFold() != null && this.fold.getOldFold().compareTo(other) == 0)
		{
			this.fold.setOldFold(this);
		}
		if (this.oldFold != null)
		{
			this.oldFold.setFold(this);
		}
		
		this.state.assertState(this);
		

		return this;
	}

/*	/**
	 * checks the lock state of the HyPeerWeb and locks it for alterations
	 * @pre this node is part of a HyPeerWeb
	 * @post the HyPeerWeb is now in a locked state, 
	 * return the node of the HyPeerWeb with id 0
	 * @return the node in the HyPeerWeb with id 0
	 */
	/*
	@SuppressWarnings("unchecked")
	public Node checkLock()
	{
			
		if (!this.getLock())
		{
			LinkedList<Thread> threads = (LinkedList<Thread>) this.getPayload("threads");
			if (threads == null)
			{
				threads = new LinkedList<Thread>();
			}
			threads.addLast(Thread.currentThread());
			this.setPayload("threads", threads);
			Thread.currentThread().suspend();
			return null;
		}
		
		return this;
		if(!this.getLock())
		{	
			ArrayList<Thread> threads = (ArrayList<Thread>) this.getPayload("threads");
			if (threads == null)
			{
				threads = new ArrayList<Thread>();
			}
			threads.add(Thread.currentThread());
			this.setPayload("threads", threads);
			Thread.currentThread().suspend();
			return null;
		}
		return this;
	}*/
	
	public void beingModified(boolean state) throws InterruptedException
	{
		boolean tryAgain = true;
		while (tryAgain)
		{
			if(accessingData > 0)
			{
				this.modifyingCommands.acquire();
			}
			synchronized (this)
			{
				if(accessingData > 0)
				{
					tryAgain = true;
					continue;
				}
				else
				{
					tryAgain = false;
				}
				if(state)
				{
					beingModified = state;
				}
				else
				{
					beingModified = state;
					while (access.hasQueuedThreads())
					{
						access.release();
					}
				}
			}
		}
	}
	
	public synchronized boolean getInsertionLock()
	{
		Semaphore busy = (Semaphore) this.getPayload("busy");
		if (busy == null || !busy.tryAcquire())
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	
	public synchronized void releaseAccessPriviledge()
	{
		accessingData--;
		if(accessingData == 0)
		{
			while (modifyingCommands.hasQueuedThreads())
			{
				modifyingCommands.release();
			}
		}
	}
	
	public synchronized boolean acquireAccessPriviledge(boolean rootAccess)
	{
		if(!rootAccess && this.beingModified)
		{
			return false;
		}
		else
		{
			accessingData++;
			return true;
		}
	}
	
	
}
